//
// Created by 高森森 on 2022/2/6.
//

#ifndef LEETCODE_SOLUTION19_H
#define LEETCODE_SOLUTION19_H

#include <iostream>
#include <vector>
#include <queue>
#include<unordered_map>

using namespace std;
class Solution19 {
    static const int RED=0;
    static const int BlUE=1;
public:
    void dfs(int cur,int color,vector<vector<vector<int>>>&graph,vector<vector<int>>&distance){
        for(auto item:graph[color][cur]) {
            if(distance[cur][color]+1<distance[item][!color]){
                distance[item][!color]=distance[cur][color]+1;
                dfs(item,!color,graph,distance);
            }

        }
    }
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<vector<int>>> graph(2, vector<vector<int>>(n, vector<int>()));
        for (vector<int>& edge : redEdges)
        {
            graph[0][edge[0]].push_back(edge[1]);
        }
        for (vector<int>& edge : blueEdges)
        {
            graph[1][edge[0]].push_back(edge[1]);
        }

        vector<vector<int>> distances(n, {INT_MAX, INT_MAX});
        // 对于起点0初始化为0，0
        distances[0] = {0, 0};
        // 考虑两种情况去遍历
        dfs(0, RED, graph, distances);
        dfs( 0,BlUE, graph, distances);

        // 再次遍历res去获取更小的值即是结果
        vector<int> res(n, -1);
        res[0] = 0;
        for (int i = 1; i < n; ++i)
        {
            int curr = min(distances[i][0], distances[i][1]);
            if (curr != INT_MAX)
            {
                res[i] = curr;
            }
        }

        return res;
    }
    vector<int> shortestAlternatingPaths2(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<vector<int>>> graph(2, vector<vector<int>>(n, vector<int>()));
        for (vector<int>& edge : redEdges)
        {
            graph[0][edge[0]].push_back(edge[1]);
        }
        for (vector<int>& edge : blueEdges)
        {
            graph[1][edge[0]].push_back(edge[1]);
        }
        vector<int>ans(n,INT_MAX);
        queue<pair<int,int>>queue;
        queue.push(make_pair(0,0));
        queue.push(make_pair(0,1));
        int step=0;
        while(!queue.empty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                int node=queue.front().first;
                int color=queue.front().second;
                queue.pop();
                ans[node]=min(ans[node],step);
                vector<int>&next=graph[color][node];
                 for(int neigh:next){
                     queue.push(make_pair(neigh,!color));
                 }
                 graph[color][node].clear();
            }
            step++;
        }
        ans[0]=0;
        for(int i=1;i<n;i++)
        {
            ans[i]=ans[i]==INT_MAX?-1:ans[i];
        }
        return ans;
    }
};


#endif //LEETCODE_SOLUTION19_H
